package 动态规划;

public class No55跳跃游戏 {

    /**
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     * 数组中的每个元素代表你在该位置[可以跳跃的最大长度]。
     * 判断你是否能够到达最后一个位置。
     *
     * 示例 1:
     * 输入: [2,3,1,1,4]
     * 输出: true
     * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
     * 示例 2:
     * 输入: [3,2,1,0,4]
     * 输出: false
     * 解释: 无论怎样，你总会到达索引为 3 的位置。
     * 但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
     */

    /**
     * 青蛙可以跳到的石头为true
     * f[i]=f[i-]
     */
    public boolean canJump(int[] nums) {
        Boolean[] dp=new Boolean[nums.length+1];
        dp[0]=true;

        for (int i = 0; i < nums.length; i++) {

            if(dp[i]!=null) {
                //可以跳到此块石头上,就开始维护此石头后面的石头
                for (int j = 1; j <= nums[i]&&(j+i)<nums.length; j++) {
                    dp[i+j]=true;
                }
            }

        }

        return dp[nums.length-1]!=null;
    }

    public static void main(String[] args) {
        No55跳跃游戏 n=new No55跳跃游戏();
        int[] arr={3,2,1,0,4};
        boolean result = n.canJump(arr);
        System.out.println(result);
    }

}
